//
// Created by LiuYou on 2021/12/6.
//

#include <iostream>
#include <vector>
#include <random>
#include <iterator>
#include <algorithm>


static int random(int left, int right) {
    std::random_device randomDevice;
    std::default_random_engine randomEngine( randomDevice());
    std::uniform_int_distribution<> uniformIntDistribution( left, right );
    return uniformIntDistribution( randomEngine );
}

//
namespace heap {
    class Heap {
    public:
        static void heapSort(std::vector<int>& arr) {
            if (arr.empty() || arr.size() == 1) {
                return;
            }

            int heapSize = arr.size();
            makeHeap( arr );

            while (heapSize > 0) {
                std::swap( arr[0], arr[--heapSize] );
                heapify( arr, 0, heapSize );
            }
        }

        static void makeHeap(std::vector<int>& arr) {
            for (int i = arr.size() - 1; i >= 0; --i) {
                heapify( arr, i, arr.size());
            }
        }

    private:
        /**
         * @brief 从下标索引 idx 开始, 构建为一个大顶堆。
         * @param arr
         * @param idx
         */
        static void heapify(std::vector<int>& arr, int idx, int heapSize) {
            int leftChildIdx = idx * 2 + 1;
            while (leftChildIdx < heapSize) {
                int greatestIdx = leftChildIdx;
                if ((leftChildIdx + 1 < heapSize) && arr[leftChildIdx + 1] > arr[leftChildIdx]) {
                    greatestIdx = leftChildIdx + 1;
                }
                if (arr[greatestIdx] > arr[idx]) {
                    std::swap( arr[greatestIdx], arr[idx] );
                    idx = greatestIdx;
                    leftChildIdx = idx * 2 + 1;
                } else {
                    break;
                }
            }
        }

    };

}


using namespace heap;


int main(int argc, char** argv) {
    {
        std::vector<int> arr( 10 );
        for (auto& item: arr) {
            item = random( 0, 100 );
        }

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << "堆: " << std::boolalpha << std::is_heap( arr.begin(), arr.end()) << "\t";
        std::cout << "有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end()) << "\t";
        std::cout << std::endl;

        Heap::heapSort( arr );
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << "堆: " << std::boolalpha << std::is_heap( arr.begin(), arr.end()) << "\t";
        std::cout << "有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end()) << "\t";
        std::cout << std::endl;
    }

    std::cout << "=================================================" << std::endl;
    {
        std::vector<int> arr( 10 );
        for (auto& item: arr) {
            item = random( 0, 100 );
        }

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << "堆: " << std::boolalpha << std::is_heap( arr.begin(), arr.end()) << "\t";
        std::cout << "有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end()) << "\t";
        std::cout << std::endl;

        Heap::makeHeap( arr );
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << "堆: " << std::boolalpha << std::is_heap( arr.begin(), arr.end()) << "\t";
        std::cout << "有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end()) << "\t";
        std::cout << std::endl;

        Heap::heapSort( arr );
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << "堆: " << std::boolalpha << std::is_heap( arr.begin(), arr.end()) << "\t";
        std::cout << "有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end()) << "\t";
        std::cout << std::endl;
    }


    return 0;
}
